package com.alex.algorithm.medium;

import com.alex.algorithm.easy.LinkedListNode;

public class AddTwoSum {

    public static void main(String[] args) {
        LinkedListNode n1 = new LinkedListNode();
        n1.setVal(2);
        LinkedListNode n2 = new LinkedListNode();
        n1.setNext(n2);
        n2.setVal(4);
        LinkedListNode n22 = new LinkedListNode();
        n22.setVal(3);
        n2.setNext(n22);
        output(n1);
        System.out.println("---");
        LinkedListNode nn1 = new LinkedListNode();
        nn1.setVal(5);
        LinkedListNode nn2 = new LinkedListNode();
        nn1.setNext(nn2);
        nn2.setVal(6);
        LinkedListNode nn22 = new LinkedListNode();
        nn22.setVal(4);
        nn2.setNext(nn22);
        output(nn1);
        System.out.println("---");
        output(addTwoSum(n1, nn1));
    }

    public static void output(LinkedListNode node) {
        LinkedListNode cur = node;
        while (cur != null) {
            System.out.println(cur.getVal());
            cur = cur.getNext();
        }
    }

    public static LinkedListNode addTwoSum(LinkedListNode l1, LinkedListNode l2) {
        if (l1 == null && l2 == null) return null;
        LinkedListNode dummyNode = new LinkedListNode();
        int carry = 0;
        LinkedListNode cur1 = l1;
        LinkedListNode cur2 = l2;
        LinkedListNode cur = dummyNode;
        while (cur1 != null && cur2 != null) {
            int v1 = (cur1.getVal() != 0 ? cur1.getVal() : 0);
            int v2 = (cur2.getVal() != 0 ? cur2.getVal() : 0);
            int sum = v1 + v2 + carry;
            LinkedListNode newNode = new LinkedListNode();
            newNode.setVal(sum % 10);
            carry = sum >=10 ? 1 : 0;
            cur.setNext(newNode);
            cur = cur.getNext();
            if (cur1 != null) {
                cur1 = cur1.getNext();
            }
            if (cur2 != null) {
                cur2 = cur2.getNext();
            }
            if (carry != 0){
                cur.setNext(new LinkedListNode(carry,null));
            }
        }
        return dummyNode.getNext();
    }
}
